\chapter{Introducci\'on}
En este cap\'itulo se hablar\'a del problema de la generaci\'on autom\'atica de RE, las contribuciones de este trabajo y el mapa de la tesis.

Suppose one wants to point out an object in Figure~\ref{GRE3D7-stimulus-graph} to an addressee. Most speakers
have no difficulty in accomplishing this task, by producing a referring expression
such as ``the green ball on the cube'' for example. Now imagine a computer being confronted
with the same task, aiming to point out individual $e3$. Assuming it has access to a
database containing all the relevant properties of the objects in the scene as shown in the figure, it needs to
find some combination of properties which applies to $e3$, and not to the other objects.
There is a choice though: There are many ways in which $e3$ can be set apart from the
rest (``the green ball on the left'', ``the small green ball'', ``the ball on the blue cube''), and
the computer has to decide which of these is optimal in the given context. Moreover,
optimality can mean different things. It might be thought, for instance, that references
are optimal when they are minimal in length, containing just enough information to
single out the target. But, as we shall see, finding minimal references is computationally
expensive, and it is not necessarily what speakers do, nor what is most useful to hearers.

So, what is Referring Expression Generation? Referring expressions play a central role
in communication, and have been studied extensively in many branches of (computational) linguistics,
 including Natural Language Generation (NLG). NLG is concerned with the process of automatically converting non-linguistic information (e.g.,
from a database such as the one illustrated in our figure) into natural language text, which is useful for practical applications
ranging from generating weather forecasts to summarizing medical information~\cite{dale2000}. Of all the subtasks of NLG, Referring Expression Generation (REG) is
among those that have received most scholarly attention. A survey of implemented,
practical NLG systems shows that virtually all of them, regardless of their purpose,
contain an REG module of some sort~\cite{Mellish2004}. This is hardly surprising
in view of the central role that reference plays in communication. A system providing
advice about air travel (White, Clark, and Moore 2010) needs to refer to flights (``the
cheapest flight'' ``the KLM direct flight''), an in-car navigation system~\cite{Drager:2012:GLN:2380816.2380908}
needs to generate spatial descriptions for areas (``take the bridge next to the church on your right''), 
and a robot dialogue system that assembles construction
toys together with a human user~\cite{foster-etal-ijcai2009} needs to refer to the components
(``insert the green bolt through the end of this red cube'').


Our goal is actually twofold. First we show how we can add non-determinism to the refinement algorithms, by replacing the fixed ordering 
over the properties of the input scene by a \emph{probability of use} for each property, and modifying the algorithm accordingly.  
In this way, each call to the algorithm can produce different REs for the same input scene and target.  We will then show that given suitable corpora of REs (like the GRE3D7 corpora discussed in~\cite{viet:gene11}) or the TUNA corpus introduced in~\cite{gatt-balz-kow:2008:ENLG} we can estimate these probability of use so that REs are generated with a probability distribution that matches those found in the corpora.  

All REG algorithms require an 
ordered list of properties that can be used to described the objects in the scene, and the naturalness of the generated REs strongly depends on this ordering. 
%coverage results reported over Viethen and 
%Dale's cabinet corpus means that \emph{some ordering} produces a reasonably wide coverage.  In other words, it has been shown that refinement algorithms have the capacity of producing REs similar to those produced by human subjects, provided a suitable ordering over relations appearing 
%in the input scene is available, but it is unclear which of all possible orders should be used.  In this article we directly address this issue.  
%The goal of this paper is twofold. First we show how we can add non-determinism and overspecification to the refinement algorithms, by replacing the fixed ordering 
%over properties of the input scene by a \emph{probability of use} for each property, and modifying the algorithm accordingly.  
%In this way, each call to the algorithm can produce different REs for the same input scene and target.  We will then show that given suitable corpora of REs (like the GRE3D7 corpora discussed in~\cite{viet:gene11}) we can estimate these probabilities of use so that REs are generated with a probability distribution that matches the one found in corpora.  

\cite{arec2:2008:Areces}
show that the refinement algorithm using the description language \el as formal language is capable of generating 67\% of 
the relational REs in the~\cite{viethen06:_algor_for_gener_refer_expres} dataset, when all possible orders of the relations in the domain are considered. This is in sharp contrast with the analysis 
done in~\cite{viethen06:_algor_for_gener_refer_expres} over the cabinet corpus, of algorithms based in Dale and Reiter's original proposal.    

As mentioned, refinement algorithms require an 
ordered list of the properties that can be used to described the objects in the scene, and the coverage results reported over Viethen and 
Dale's cabinet corpus means that \emph{some ordering} produces a reasonably wide coverage.  In other words, it has been shown that refinement algorithms have the capacity of producing REs similar to those produced by human subjects, provided a suitable ordering over relations appearing 
in the input scene is available, but it is unclear which of all possible orders should be used.  In this article we directly address this issue.  


The rest of the paper is structured as follows. In Section~\ref{sec:algorithm} we introduce the technical details of the 
refinement algorithms presented in~\cite{arec2:2008:Areces,arec:usin11} and show how to introduce non-determinism using 
the probability of use of the properties in the input scene. In this section, we assume that these probabilities are provided as 
input to the algorithm. In Section~\ref{sec:learning}, we show how to estimate the 
probability of use of a property from training data. Given corpora consisting of pairs (scene, target) together with the REs used to 
describe the target in each case, we propose a method to compute the probability of use of each property for each scene, and use a machine learning approach to generalize these properties to new targets and scenes not appearing in the corpora. 

Testing of the resulting algorithms shows that there is still one factor missing to property account for the REs found in corpora: overspecification.  Refinement algorithms only allow a mild form of over-specification in the REs produced.  We discuss this in 
Section~\ref{sec:overspecification} and propose a modification that let the algorithm generate overspecified, but non trivially redundant RE.  The modification proposed is inspired by the work of~\cite{keysar:Curr98}, on the egocentric basis of language.  
Section~\ref{sec:evaluation} presents a quantitative evaluation of the resulting algorithm and discusses interesting examples \textit{over the GRE3D7 and the TUNA-corpus}. 
We show that when trained with scenes from the GRE3D7 corpora the algorithm can generate REs with a probability distribution that, 
in certain scenes, coincides with an up to 84.49\% of accuracy with the probability distribution of REs used by humans for that scene. 
\textit{We compare our results with the TUNA-corpus with results of the ASGRE challenge and show better results than the adquire for the best system in 2008.
In Section~\ref{sec:error} we show an interesting analysis of errors that can be taken into account in the next works.}, then in Section~\ref{sec:related-work} we describe related work in the area.

In Section~\ref{sec:discussion} we discuss motivations and future lines of research, focusing on recent work discussing the role 
of non-determinism and over-specification in the generation of referring expressions. 

\section{Descripci\'on del problema}
\label{sec:intro}

En ling\"u\'{i}stica, una expresi\'on referencial (RE que viene de la expresi\'on en ingl\'es referring expression) es una expresi\'on que identifica un\'ivocamente a un objeto de para un interlocutor, desde un conjunto de posibles distractores. Por ejemplo si nosotros queremos identificar a un cierto animal d de un conjunto de mascotas, la expresi\'on ``el perro'' ser\'a RE si d es el \'unico perro en el conjunto, y si nosotros estamos seguros que nuestro interlocutor identificar\'a a d como un perro. Para una persona esto ser\'ia una tarea f\'acil de realizar, pensemos ahora como lo har\'ia una computadora, supongamos que queremos conseguir un algoritmo que genere autom\'aticamente esas expresiones referenciales que la gente genera. Una propiedad es una caracter\'istica de una entidad particular por ejemplo, la raza de un perro, el tener o no tener bigotes para un hombre, o el color para un objeto, cada entidad puede tener muchas propiedades, e incluso puede tener relaciones, as\'i como las relaciones familiares, las relaciones con respecto a la posici\'on f\'isica, etc. Para que una computadora pueda generar las RE generadas por las personas, primero deber\'ia seleccionar las propiedades y/o relaciones que se incluir\'an en la RE, deber\'a tener una base de datos conteniendo las propiedades y relaciones relevantes de la escena, podemos imaginar que una computadora podr\'a generar muchas m\'as expresiones referenciales que una persona, este es un desaf\'io que direccionaremos en esta tesis, nuestra meta ser\'a imitar al humano en la generaci\'on de expresiones referenciales. Esta selecci\'on de la RE m\'as apropiada tambi\'en debe tener en cuenta al interlocutor, es natural que los humanos demos distintas RE a distintos interlocutores. En el \'area muchas veces se habla de optimalidad de la RE, pero con diferentes significados, para algunos una RE \'optima es aquella que dice lo m\'inimo necesario para identificar al objeto target, para otros es la menos esfuerzo requiere del interlocutor para identificarlo
Usamos generaci\'on de RE todo el tiempo en la vida real, y as\'i los sistemas tambi\'en las usan, por lo tanto son necesarios los algoritmos para generarlas autom\'aticamente, las RE han sido estudiadas y tienen muchas aplicaciones pr\'acticas desde generaci\'on de reportes meteorol\'ogicos a generaci\'on autom\'atica de res\'umenes de informaci\'on m\'edica~\cite{dale2000}. Muchos sistemas de GLN incluyen un m\'odulo de GER~\cite{Mellish2004}.
Las expresiones referenciales ocupan un papel central en la comunicaci\'on, popr ejemplo sistemas que proveen advertencias en navegaci\'on aerea
 (White, Clark, and Moore 2010) necesitan referirse a los vuelos, en sistemas de navegaci\'on en auto~\cite{Drager:2012:GLN:2380816.2380908} se necesitan generar descripciones espaciales para \'areas (tomar la siguiente calle a la derecha de la iglesia), y sistemas de di\'alogo con un robot que ensambla piezas para la contrucci\'on de juguetes~\cite{foster-etal-ijcai2009} necesita referirse a las piezas (insert\'a el tornillo verde en el cubo)

%Our goal is actually twofold. First we show how we can add non-determinism to the
%refinement algorithms, by replacing the fixed ordering over the properties of the input scene
%by a probability of use for each property, and modifying the algorithm accordingly. In this
%way, each call to the algorithm can produce different REs for the same input scene and
%target. We will then show that given suitable corpora of REs (like the GRE3D7 corpora
%discussed in (Viethen, 2011)) ot the TUNA corpus introduced in (Gatt et al., 2008) we can
%estimate these probability of use so that REs are generated with a probability distribution
%that matches those found in the corpora.
%All REG algorithms require an ordered list of properties that can be used to described
%the objects in the scene, and the naturalness of the generated REs strongly depends on this
%ordering.
%(Areces et al., 2008) show that the refinement algorithm using the description language
%EL as formal language is capable of generating 67\% of the relational REs in the (Viethen &
%Dale, 2006) dataset, when all possible orders of the relations in the domain are considered.
%This is in sharp contrast with the analysis done in (Viethen & Dale, 2006) over the cabinet
%corpus, of algorithms based in Dale and Reiter's original proposal.
%As mentioned, refinement algorithms require an ordered list of the properties that can
%be used to described the objects in the scene, and the coverage results reported over Viethen
%and Dale's cabinet corpus means that some ordering produces a reasonably wide coverage.
%In other words, it has been shown that refinement algorithms have the capacity of producing
%REs similar to those produced by human subjects, provided a suitable ordering over relations
%appearing in the input scene is available, but it is unclear which of all possible orders should
%be used. In this article we directly address this issue.
%The rest of the paper is structured as follows. In Section 3 we introduce the technical
%details of the refinement algorithms presented in (Areces et al., 2008, 2011) and show how
%to introduce non-determinism using the probability of use of the properties in the input
%scene. In this section, we assume that these probabilities are provided as input to the
%algorithm. In Section 4, we show how to estimate the probability of use of a property from
%training data. Given corpora consisting of pairs (scene, target) together with the REs used
%to describe the target in each case, we propose a method to compute the probability of use
%of each property for each scene, and use a machine learning approach to generalize these
%properties to new targets and scenes not appearing in the corpora.
%Testing of the resulting algorithms shows that there is still one factor missing to prop-
%erty account for the REs found in corpora: overspecification. Refinement algorithms only
%allow a mild form of over-specification in the REs produced. We discuss this in Section 5
%and propose a modification that let the algorithm generate overspecified, but non trivially
%redundant RE. The modification proposed is inspired by the work of (Keysar et al., 1998),
%on the egocentric basis of language. Section 6 presents a quantitative evaluation of the
%resulting algorithm and discusses interesting examples over the GRE3D7 and the TUNA-
%corpus. We show that when trained with scenes from the GRE3D7 corpora the algorithm
%can generate REs with a probability distribution that, in certain scenes, coincides with an
%up to 84.49\% of accuracy with the probability distribution of REs used by humans for that
%scene. We compare our results with the TUNA-corpus with results of the ASGRE challenge
%and show better results than the adquire for the best system in 2008. In Section 7 we show
%an interesting analysis of errors that can be taken into account in the next works., then in
%Section 8 we describe related work in the area.
%In Section 9 we discuss motivations and future lines of research, focusing on recent work
%discussing the role of non-determinism and over-specification in the generation of referring
%expressions.

Suppose one wants to point out an object in Figure~\ref{GRE3D7-stimulus-graph} to an addressee. Most speakers
have no difficulty in accomplishing this task, by producing a referring expression
such as ``the green ball on the cube'' for example. Now imagine a computer being confronted
with the same task, aiming to point out individual $e3$. Assuming it has access to a
database containing all the relevant properties of the objects in the scene as shown in the figure, it needs to
find some combination of properties which applies to $e3$, and not to the other objects.
There is a choice though: There are many ways in which $e3$ can be set apart from the
rest (``the green ball on the left'', ``the small green ball'', ``the ball on the blue cube''), and
the computer has to decide which of these is optimal in the given context. Moreover,
optimality can mean different things. It might be thought, for instance, that references
are optimal when they are minimal in length, containing just enough information to
single out the target. But, as we shall see, finding minimal references is computationally
expensive, and it is not necessarily what speakers do, nor what is most useful to hearers.

So, what is Referring Expression Generation? Referring expressions play a central role
in communication, and have been studied extensively in many branches of (computational) linguistics, including Natural Language Generation (NLG). NLG is concerned with the process of automatically converting non-linguistic information (e.g.,
from a database such as the one illustrated in our figure) into natural language text, which is useful for practical applications
ranging from generating weather forecasts to summarizing medical information~\cite{dale2000}. Of all the subtasks of NLG, Referring Expression Generation (REG) is
among those that have received most scholarly attention. A survey of implemented,
practical NLG systems shows that virtually all of them, regardless of their purpose,
contain an REG module of some sort~\cite{Mellish2004}. This is hardly surprising
in view of the central role that reference plays in communication. A system providing
advice about air travel (White, Clark, and Moore 2010) needs to refer to flights (
